<html>
<head><meta charset="utf-8"><title>notes on datafrog · t-compiler/wg-polonius · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/index.html">t-compiler/wg-polonius</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html">notes on datafrog</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="176497493"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176497493" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176497493">(Sep 24 2019 at 19:30)</a>:</h4>
<p>I've mentioned in the list from a while ago, that there was possible work to be done in datafrog: I've looked at a couple of easy ones recently and will explain this here</p>



<a name="176497657"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176497657" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176497657">(Sep 24 2019 at 19:32)</a>:</h4>
<p>the 1st thing was the idea of more specialized Relations, that is, right now they're all Vec of tuples</p>



<a name="176497672"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176497672" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176497672">(Sep 24 2019 at 19:32)</a>:</h4>
<p>very general, always works, <span aria-label="thumbs up" class="emoji emoji-1f44d" role="img" title="thumbs up">:thumbs_up:</span></p>



<a name="176497726"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176497726" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176497726">(Sep 24 2019 at 19:33)</a>:</h4>
<p>in some cases, they might consume too much memory, or we're not using the flexibility</p>



<a name="176497849"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176497849" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176497849">(Sep 24 2019 at 19:34)</a>:</h4>
<p>example: <code>killed</code> we're propagating loans in origins along the CFG <em>if</em> the loan is not <code>killed</code> at a specific point</p>



<a name="176497902"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176497902" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176497902">(Sep 24 2019 at 19:34)</a>:</h4>
<p>we're never using this relation to produce tuples</p>



<a name="176497941"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176497941" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176497941">(Sep 24 2019 at 19:35)</a>:</h4>
<p>thus, we don't really need the data, we only need to know if a specific tuple is absent from this relation</p>



<a name="176498042"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176498042" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176498042">(Sep 24 2019 at 19:36)</a>:</h4>
<p>for this use-case there could be a specific type of Relation, only interested in the absence of data, for example using a probabilistic data structure like a Bloom filter (or just a Set, that also works faster than the Vec, but uses more memory than a filter/bitmap)</p>



<a name="176498243"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176498243" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176498243">(Sep 24 2019 at 19:38)</a>:</h4>
<p>the <code>killed</code> relation is usually pretty small I think, esp compared to the others, but <code>clap</code> had the biggest one at 1000 in our dataset (and I haven't looked at dumping p.rl.o facts yet, but <span class="user-mention" data-user-id="204115">@Albin Stjerna</span>  has some of those benchmarks and then some, so maybe they'll have confirmation or infirmation on this) so the memory saving would be "small" in the absolute (but big in the relative reduction) for relatively the same query performance, at this size</p>



<a name="176498294"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176498294" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176498294">(Sep 24 2019 at 19:39)</a>:</h4>
<p>after this <code>filter_anti</code> Leaper specialized case, there's also the "filtering" case</p>



<a name="176498421"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176498421" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176498421">(Sep 24 2019 at 19:41)</a>:</h4>
<p><code>extend_with</code> is also somehow used for filtering, because <code>filter_with</code> is for semijoins with the source Relation</p>



<a name="176498608"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176498608" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176498608">(Sep 24 2019 at 19:43)</a>:</h4>
<p>but it's made for <code>proposing</code> as well, so there's some work done in <code>count</code> to prepare for that (<a href="https://github.com/rust-lang/datafrog/blob/master/src/treefrog.rs#L364-L371" target="_blank" title="https://github.com/rust-lang/datafrog/blob/master/src/treefrog.rs#L364-L371">here</a>) again it's not much but there are more counts than intersections in the filtering case so this could be done in <code>intersect</code> instead when filtering</p>



<a name="176498717"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176498717" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176498717">(Sep 24 2019 at 19:44)</a>:</h4>
<p>in the same idea, we're not using <code>region_live_at</code> to produce tuples either</p>



<a name="176498741"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176498741" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176498741">(Sep 24 2019 at 19:44)</a>:</h4>
<p>therefore another Relation dedicated to filtering could be tried</p>



<a name="176498895"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176498895" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176498895">(Sep 24 2019 at 19:46)</a>:</h4>
<p>and there's a single index</p>



<a name="176499022"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176499022" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176499022">(Sep 24 2019 at 19:48)</a>:</h4>
<p>just to have an example, what I've tried here was just an fx map of fx sets — the construction is slower, and the Relation is quite big, but it does make a relative difference on <code>clap</code> (which is the only benchmark I had tried in all these tests)</p>



<a name="176499288"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176499288" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176499288">(Sep 24 2019 at 19:51)</a>:</h4>
<p>setting up the data shouldn't be much of a concern, esp compared to what we do right now, where rustc builds Vecs, which are cloned a bit, sorted and deduplicated, we materialize the free regions everywhere on the CFG, compute liveness and some things about initialization (which I assume is related to liveness as well), sometimes multiples times etc :) but we'll get there</p>



<a name="176499532"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176499532" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176499532">(Sep 24 2019 at 19:54)</a>:</h4>
<p>ideally we should be getting the Relations, all ready to go, in the variants — but ofc there's slight caveat that Variables take ownership of them so this can probably only partially be done now; at least to fix the easy issue of the Hybrid variant</p>



<a name="176499640"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176499640" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176499640">(Sep 24 2019 at 19:55)</a>:</h4>
<p>on another theme, all the Relations, Variables, Leapers etc are very generic in datafrog, and generics + a crate dependency = no inlining opportunities; so that's an easy PR right there :)</p>



<a name="176499824"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176499824" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176499824">(Sep 24 2019 at 19:57)</a>:</h4>
<p>and lastly for now, is the WF-ness of leapjoins: <a href="https://github.com/rust-lang/datafrog/blob/master/src/treefrog.rs#L26" target="_blank" title="https://github.com/rust-lang/datafrog/blob/master/src/treefrog.rs#L26">this assert</a> bakes the fact that a leapjoin should produce some tuples</p>



<a name="176499922"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176499922" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176499922">(Sep 24 2019 at 19:58)</a>:</h4>
<p>however</p>
<div class="codehilite"><pre><span></span>errors(B, P) :-
   requires(R, B, P),
   invalidates(B, P),
   region_live_at(R, P).
</pre></div>


<p>is only filtering <code>requires</code></p>



<a name="176500016"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176500016" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176500016">(Sep 24 2019 at 19:59)</a>:</h4>
<p>relaxing this constraint wouldn't by itself make a lot of things faster, it's just the regular joins, however, it could allow removing some indexes</p>



<a name="176500131"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176500131" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176500131">(Sep 24 2019 at 20:00)</a>:</h4>
<p>and maintaining those, especially with bigger relations like 2 out of the 3 here, can matter</p>



<a name="176500228"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176500228" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176500228">(Sep 24 2019 at 20:01)</a>:</h4>
<p>there might be a small Leaper (like the ValueFilter/PrefixFilter) we could add to just pass through the source tuples, so that the leapjoin feels like tuples are produced even though they are just going down the chain to be filtered by the next 2 leapers</p>



<a name="176500470"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176500470" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176500470">(Sep 24 2019 at 20:04)</a>:</h4>
<p>I haven't done anything for this last point, while for the others I have experiments here and there (which I accidentally depended on in the previous equality-tracking prototype) so if anyone is interested, this could be a thing to look at</p>



<a name="176500699"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176500699" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176500699">(Sep 24 2019 at 20:06)</a>:</h4>
<p>(also another easy one, in moving from the original leapjoin API of an array of Leapers, to the tuple of Leapers datafrog uses now, we have "lost" the ability to have a leapjoin with a single <code>extend_with</code> leaper — again, not really efficiency-critical except maybe removing indexes, and that should be a one-line PR)</p>



<a name="176502947"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176502947" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanda Stjerna <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176502947">(Sep 24 2019 at 20:30)</a>:</h4>
<blockquote>
<p>the <code>killed</code> relation is usually pretty small I think, esp compared to the others, but <code>clap</code> had the biggest one at 1000 in our dataset (and I haven't looked at dumping p.rl.o facts yet, but <span class="user-mention silent" data-user-id="204115">Albin Stjerna</span>  has some of those benchmarks and then some, so maybe they'll have confirmation or infirmation on this) so the memory saving would be "small" in the absolute (but big in the relative reduction) for relatively the same query performance, at this size</p>
</blockquote>
<p>I'll read and reply tomorrow, but yes, <code>killed</code> is relatively small. Still, I suspect it could do with compression. <a href="/user_uploads/4715/oqJOAre15ij4zHXuzGaEfSPW/input_sizes_boxplot.png" target="_blank" title="input_sizes_boxplot.png">Here is a box plot of the number of tuples in my dataset!</a>!</p>
<div class="message_inline_image"><a href="/user_uploads/4715/oqJOAre15ij4zHXuzGaEfSPW/input_sizes_boxplot.png" target="_blank" title="Here is a box plot of the number of tuples in my dataset!"><img src="/user_uploads/4715/oqJOAre15ij4zHXuzGaEfSPW/input_sizes_boxplot.png"></a></div>



<a name="176503237"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176503237" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanda Stjerna <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176503237">(Sep 24 2019 at 20:33)</a>:</h4>
<p>Speaking of this, we don't really need to compute liveness for <em>every</em> variable, right? We only need them if they "connect" to an origin either in the variable's type, or in a reference inside of a struct that implements its own drop? I think there is definitely some filtering that can be done here too.</p>



<a name="176503475"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176503475" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176503475">(Sep 24 2019 at 20:35)</a>:</h4>
<p>a lot of filtering can be done indeed, for example when a value ultimately flows into 'static</p>



<a name="176503561"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176503561" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176503561">(Sep 24 2019 at 20:36)</a>:</h4>
<p>and thank you for the tuple numbers :)</p>



<a name="176565784"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176565784" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanda Stjerna <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176565784">(Sep 25 2019 at 13:46)</a>:</h4>
<p>Actually, I think all the inputs relating to variables are just used for filtering as well, but that may be positive filtering, but I suspect this is best solved at the fact generation phase (i.e. only emitting liveness inputs for variables we actually may care about the liveness of)</p>



<a name="176565944"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176565944" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanda Stjerna <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176565944">(Sep 25 2019 at 13:48)</a>:</h4>
<p><span class="user-mention" data-user-id="116113">@lqd</span> In your benchmarks, how are you measuring time? Do you use the complete solve-time or just the "borrow check" part of it, ignoring liveness? I'm worried that liveness now occupies a very large portion of the runtime, given how the correlations between total runtime and input variable sizes look (number of variables and other very liveness-related inputs completely dominate.</p>



<a name="176565953"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176565953" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanda Stjerna <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176565953">(Sep 25 2019 at 13:48)</a>:</h4>
<p>I really want to fix that benchmark mode</p>



<a name="176566024"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176566024" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176566024">(Sep 25 2019 at 13:49)</a>:</h4>
<p>I'm benchmarking the analysis itself so I'm only using the computation_start.elapsed() value, the rest is either counting reading files and interning, cloning data, or computing other things</p>



<a name="176566210"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176566210" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176566210">(Sep 25 2019 at 13:51)</a>:</h4>
<p>(this should all probably go in a dedicated topic but yes liveness filtering should be probably done in rustc like it's done in NLL)</p>



<a name="176567146"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176567146" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanda Stjerna <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176567146">(Sep 25 2019 at 14:00)</a>:</h4>
<blockquote>
<p>I'm benchmarking the analysis itself so I'm only using the computation_start.elapsed() value, the rest is either counting reading files and interning, cloning data, or computing other things</p>
</blockquote>
<p>Ok, so you measure liveness computations and everything?</p>



<a name="176568663"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176568663" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176568663">(Sep 25 2019 at 14:16)</a>:</h4>
<p>no liveness and initialization is done before creating the analysis timer, <a href="https://github.com/rust-lang/polonius/blob/master/polonius-engine/src/output/naive.rs#L51-L223" target="_blank" title="https://github.com/rust-lang/polonius/blob/master/polonius-engine/src/output/naive.rs#L51-L223">this</a> is what I'm measuring</p>



<a name="176568768"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176568768" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanda Stjerna <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176568768">(Sep 25 2019 at 14:17)</a>:</h4>
<p>Ah, ok. Fair enough!</p>



<a name="176568778"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176568778" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanda Stjerna <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176568778">(Sep 25 2019 at 14:17)</a>:</h4>
<p>So then we don't know if those explode completely</p>



<a name="176568785"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176568785" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanda Stjerna <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176568785">(Sep 25 2019 at 14:17)</a>:</h4>
<p>Which, I guess, makes sense</p>



<a name="176570270"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176570270" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176570270">(Sep 25 2019 at 14:33)</a>:</h4>
<p>they do not explode completely on what I've tried, eg clap, where Naive + filtering is like &lt;300ms, including liveness/initialization/analysis and a couple clones here and there ^^</p>



<a name="176573092"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176573092" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanda Stjerna <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176573092">(Sep 25 2019 at 15:00)</a>:</h4>
<p>I'm really looking forward to some systematic benchmarking at some point though :)</p>



<a name="176573127"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/176573127" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanda Stjerna <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#176573127">(Sep 25 2019 at 15:01)</a>:</h4>
<p>In particular if we could get continuous benchmarking</p>



<a name="183959661"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/183959661" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#183959661">(Dec 20 2019 at 18:21)</a>:</h4>
<p>I was trying to write benchmarks about the specialized-relations for datafrog antijoins idea, and stumbled upon the fact that <code>Relation::from_antijoin</code> does not work at all</p>



<a name="183959703"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/notes%20on%20datafrog/near/183959703" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/notes.20on.20datafrog.html#183959703">(Dec 20 2019 at 18:21)</a>:</h4>
<p>(but I'll fix it, probably next week)</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>